//    Copyright 2009-2011 Ateeq Sharfuddin, Xiaofan Feng.
//    This file is part of Project Viatei.
//
//    Project Viatei is free software: you can redistribute it and/or modify
//    it under the terms of the GNU Lesser General Public License as published by
//    the Free Software Foundation, either version 3 of the License, or
//    (at your option) any later version.
//
//    Project Viatei is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//    GNU Lesser General Public License for more details.
//
//    You should have received a copy of the GNU Lesser General Public License
//    along with Project Viatei.  If not, see <http://www.gnu.org/licenses/>.

#include <vector>

#include "delta2.h"

namespace boyermoore
{
	std::vector<wordi_t> suffixes(const std::string & pattern)
	{
		const wordi_t len = pattern.length();
		wordi_t f, g;
		
		std::vector<wordi_t> suffixArray;
		suffixArray.resize(pattern.length());
		
		suffixArray[ len - 1 ] = len;
		g = len - 1;
		
		for ( wordi_t i = len - 2 ; i >= 0 ; --i )
		{
			if ( i > g && suffixArray[ i + len - 1 - f ] < i - g )
				suffixArray[ i ] = suffixArray[ i + len - 1 - f ];
			else
			{
				if ( i < g )
					g = i;
				
				f = i;
				
				while ( g >= 0 && pattern[ g ] == pattern[ g + len - 1 - f ] )
					--g;

				suffixArray[ i ] = f - g;
			}
		}
		
		return suffixArray;
	}
	
	std::vector<wordi_t> delta2(const std::string & pattern)
	{
		wordi_t i, j;
		
		const wordi_t len = pattern.length();
		
		std::vector<wordi_t> delta2(len);
		std::vector<wordi_t> suffixArray = boyermoore::suffixes(pattern);
		
		
		for ( i = 0 ; i < len ; ++i )
			delta2[ i ] = len;
		
		j = 0;
		for ( i = len - 1; i >= 0 ; --i )
			if ( suffixArray[ i ] == i + 1 )
				for ( ; j < len - 1 - i; ++j )
					if ( delta2[ j ] == len )
						delta2[ j ] = len - 1 - i;
		
		for (i = 0; i <= len - 2; ++i)
			delta2[ len - 1 - suffixArray[i] ] = len - 1 - i;
		
		return delta2;
	}
	
}